
package com.huawei.common.okhttp;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

/**
 * 功能描述
 *
 * @author cWX1142527
 * @since 2023年01月18日
 */
public class Java_496_下一个更大元素 {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String[] nums1 = scanner.nextLine().split(",");
            String[] nums2 = scanner.nextLine().split(",");
            maxNextNum(nums1, nums2);
            duipai(nums1, nums2);
        }
    }

    public static String maxNextNum(String[] nums1, String[] nums2) {
        // 保持存储结果
        Map<Integer, Integer> allExtMap = new HashMap();
        Stack<Integer> stack = new Stack<>();
        for (String num : nums2) {
            int curerentNum = Integer.valueOf(num);
            // 大于栈顶元素时，栈顶元素存在下一个最大元素 curerentNum ，弹出栈顶后继续判断新的栈顶与当前数据的对比
            while (!stack.isEmpty()) {
                int topVal = stack.peek();
                if (curerentNum > topVal) {
                    stack.pop();
                    allExtMap.put(topVal, curerentNum);
                    continue;
                } else {
                    // 不大于下个元素时
                    stack.push(curerentNum);
                    break;
                }
            }
            if (stack.isEmpty()) {
                stack.push(curerentNum);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < nums1.length; i++) {
            int val = Integer.valueOf(nums1[i]);
            if (allExtMap.containsKey(val)) {
                stringBuilder.append(allExtMap.get(val));
            } else {
                stringBuilder.append("-1");
            }
            if (i < nums1.length - 1) {
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        System.out.println("正常结果：" + stringBuilder);
        return stringBuilder.toString();
    }

    public static String duipai(String[] nums1, String[] nums2) {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < nums1.length; i++) {
            String tmpVal = nums1[i];
            boolean isStart = false;
            String nextMaxNum = "-1";
            for (int j = 0; j < nums2.length; j++) {
                if (tmpVal.equals(nums2[j])) {
                    isStart = true;
                }
                if (isStart && nums2[j].compareTo(tmpVal) > 0) {
                    nextMaxNum = nums2[j];
                    break;
                }
            }
            stringBuilder.append(nextMaxNum);
            if (i < nums1.length - 1) {
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        System.out.println("对拍结果：" + stringBuilder);
        return stringBuilder.toString();
    }
}
